package com.ywgt;

/**
 * 插值查找
 */
public class InsertSearch {
    public static void main(String[] args) {
        int [] arr=new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i]= i+2;
        }
        int index = getIndex(arr, 0, arr.length - 1, 100);
        System.out.println(index);

    }

    public static int getIndex(int [] arr,int left,int right,int val){
        if(left>right||val<arr[left]||val>arr[right]){
            return -1;
        }
        int mid=left+(right-left)*(val-arr[left])/(arr[right]-arr[left]);
        if(arr[mid]>val){
            return getIndex(arr,left,mid-1,val);
        }
        if(arr[mid]<val){
            return getIndex(arr,mid+1,right,val);
        }else {
            return mid;
        }
    }
}
